class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False
        stack = list()
        pair = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        for ch in s:
            if ch in pair:
                if not stack or stack[-1] != pair[ch]:
                    return False
                else:
                    stack.pop()
            else:
                stack.append(ch)
        return not stack